//
//  graph.h
//  math
//
//  Created by Sam Jaffe on 11/2/12.
//  Copyright (c) 2012 Sam Jaffe. All rights reserved.
//

#pragma once

#include <utility>
#include <set>
#include <functional>
#include <map>
#include <list>
#include <algorithm>
#include <limits>
#include <vector>

#include "../unordered_pair/unordered_pair.hpp"

#pragma mark typedefs and prototypes
// A graph is an ordered pair (V, E) V = vertexes, E = edges
// A digraph is an ordered pair (V, A) A = arcs (directed edges)
namespace math {
    namespace graph {
        template<class I>
        class graph;
        
        template<class I>
        class digraph;
        
        template<class I>
        class tree;
        
        template<class I>
        class node;        
    }
}

#pragma mark class definitions
namespace math {
    namespace graph {
        template <class I>
        class node {
        private:
            I title;
        public:
            constexpr node() {}
            node(const I& title) :
            title(title) {
                
            }
            
            bool operator< (const node<I>& other) const {return title < other.title;}
            const I& operator ()() {return title;}
        };
        
        template <class I>
        class graph {
        public:
            typedef node<I> vertex;
            typedef unordered_pair<vertex> edge;
            typedef std::set<vertex> verticies;
            typedef std::multimap<vertex, vertex> edges;
            
            typedef std::function<double(const edge&)> weighing;

        private:
            std::set<vertex> V;
            std::multimap<vertex, vertex> E;
        public:
            constexpr graph() {}
            
            graph(const verticies& v, const edges& e) :
            V(v),
            E(e) {
                
            }
            
            bool addVertex(const vertex& n) {
                return V.insert(n).second;
            }
            
            virtual void link(const vertex& head, const vertex& tail) {
                E.insert(std::make_pair(head, tail));
                E.insert(std::make_pair(tail, head));
            }
            
            verticies& getVertex() {
                return V;
            }
            
            virtual edges& getEdges() {
                return E;
            }
            
            const verticies& getVertex() const {
                return V;
            }
            
            virtual const edges& getEdges() const {
                return E;
            }
        };
                
        template <class I>
        class digraph {
        public:
            typedef node<I> vertex;
            typedef std::pair<vertex, vertex> arc;
            typedef std::set<vertex> verticies;
            typedef std::multimap<vertex, vertex> arcs;
            
            typedef std::function<double(const arc&)> weighing;
        private:
            std::set<vertex> V;
            std::multimap<vertex, vertex> A;
        public:
            constexpr digraph() {}
            
            digraph(const verticies& v, const arcs& a) :
            V(v),
            A(a) {
                
            }
            
            bool addVertex(const vertex& n) {
                return V.insert(n).second;
            }
            
            void link(const vertex& head, const vertex& tail) {
                getArcs().insert(std::make_pair(head, tail));
            }
            
            verticies& getVertex() {
                return V;
            }
            
            const verticies& getVertex() const {
                return V;
            }
            
            arcs& getArcs() {
                return A;
            }
            
            const arcs& getArcs() const {
                return A;
            }
            
        };
        
        template <class I>
        graph<I> kruskal(const graph<I>& g, typename graph<I>::weighing w) {
            std::vector<std::pair<node<I>, node<I>> > E_s(g.getEdges().size());
            for (auto e : g.getEdges()) {
                E_s.push_back(e);
            }
            std::sort(E_s.begin(), E_s.end(),
                      [&w] (const std::pair<node<I>, node<I>>& a,
                            const std::pair<node<I>, node<I>>& b) {
                          return w(a) < w(b);
                      });
            
            std::set<node<I>> V_prime;
            std::multimap<node<I>, node<I>> E_prime;
            
            for (auto it = E_s.begin(); it != E_s.end(), V_prime.size() < g.getVertex().size(); it++) {
                node<I> &u = it->first, &v = it->second;
                if (V_prime.find(u) == V_prime.end() && V_prime.find(v) == V_prime.end()) {
                    V_prime.insert(u);
                    V_prime.insert(v);
                    E_prime.emplace(u, v);
                    E_prime.emplace(v, u);
                }
            }
            return graph<I>(V_prime, E_prime);
        }
        
        template <class I>
        graph<I> prim(const graph<I>& g, typename graph<I>::weighing w);

        
        template <class I>
        std::tuple<std::function<double(const node<I>&)>,
                   std::function<node<I>(const node<I>&)> >
        dijkstra(const digraph<I>& d, typename digraph<I>::weighing w, const node<I>& root) {
            std::set<node<I>> explored, frontier, unexplored;
            std::map<node<I>, double> distance;
            std::map<node<I>, node<I>> predecessor;
            frontier.insert(root);
            for (auto n : d.getVertex()) {
                unexplored.insert(n);
                distance[n] = std::numeric_limits<double>::infinity();
            }
            unexplored.erase(root);
            distance[root] = 0.0D;
            while (!frontier.empty()) {
                node<I> min = *frontier.begin();
                for (auto n : frontier) {
                    if (distance[n] < distance[min])
                        min = n;
                }
                double minlen = distance[min];
                auto arcs = d.getArcs().equal_range(min);
                for(auto it = arcs.first; it != arcs.second; it++) {
                    auto& u = it->first;
                    if (minlen + w(*it) < distance[u]) {
                        distance[u] = minlen + w(*it);
                        frontier.insert(u);
                        unexplored.erase(u);
                        predecessor[u] = min;
                    }
                }
                explored.insert(min);
                frontier.erase(min);
            }
            return std::make_tuple([distance](const node<I>& n){return distance.at(n);}, [predecessor](const node<I>& n){return predecessor.at(n);});
        }
               
        template <class I>
        std::tuple<std::function<double(const node<I>&)>,
                   std::function<node<I>(const node<I>&)> >
        bellman_ford(const digraph<I>& d, typename digraph<I>::weighing w, const node<I>& r) {
            std::map<node<I>, double> distance;
            std::map<node<I>, node<I>> predecessor;
            
            for (auto n : d.getVertex())
                distance[n] = std::numeric_limits<double>::infinity();
            
            for (int i = 1; i < d.getVertex().size(); i++) {
                for (auto e : d.getArcs()) {
                    if (distance[e.first] + w(e) < distance[e.second]) {
                        distance[e.second] = distance[e.first] + w(e);
                        predecessor[e.second] = e.first;
                    }
                }
            }
            
            for (auto e : d.getArcs()) {
                if (distance[e.first] + w(e) < distance[e.second])
                    throw "Graph contains a negative cycle!";
            }
            
            return std::make_tuple([distance](const node<I>& n){return distance[n];}, [predecessor](const node<I>& n){return predecessor[n];});
        }
        
        void floyd_warshall();
        
    }
}

#pragma mark inline functions
